package bank;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class _19RemoveNthNode {
    /**
     * 先来看看递归的代码
     * 慢慢来吧，以后可以学会的
     * int cur = 0;
     * public static ListNode removeNthFromEnd(ListNode head, int n) {
     * if(head == null) return null;
     * head.next = removeNthFromEnd(head.next,n);
     * cur++;
     * if(n == cur) return head.next;
     * return head;
     * }
     */
    public static ListNode19 removeNthFromEnd(ListNode19 head, int n) {
        //常规思路
        //先遍历链表，算出长度
        int len = listLen(head);
        if (n == len) return head.next;
        int nPre = len - n;
        ListNode19 node = head;
        for (int i = 1; i <= len; i++) {
            if (i != nPre) {
                node = node.next;
                continue;
            } else {
                node.next = node.next.next;
                break;
            }
        }
        return head;
    }

    private static int listLen(ListNode19 head) {
        if (head == null) return 0;
        int len = 1;
        for (ListNode19 node = head; node.next != null; len++) {
            node = node.next;
        }
        return len;
    }

    public class ListNode19 {
        int val;
        ListNode19 next;

        ListNode19() {
        }

        ListNode19(int val) {
            this.val = val;
        }

        ListNode19(int val, ListNode19 next) {
            this.val = val;
            this.next = next;
        }
    }
}
